#include<bits/stdc++.h>
using namespace std;
class Graph {
public:
typedef pair<int,int> pii;
    vector<vector<pii>> g;
    Graph(int n, vector<vector<int>>& edges) {
        g=vector<vector<pii>>(n);
        for(auto it:edges)
        {
            int a=it[0],b=it[1],c=it[2];
            g[a].emplace_back(b,c);
        }
    }
    
    void addEdge(vector<int> edge) {
        g[edge[0]].emplace_back(edge[1],edge[2]);
    }
    
    int shortestPath(int n1, int n2) {
        priority_queue<pii,vector<pii>,greater<pii>> q;
        int n=g.size();
        vector<int> d(n,INT_MAX);
        d[n1]=0;
        q.emplace(0,n1);
        while(!q.empty())
        {
            auto [dist_x,x]=q.top();
            q.pop();
            if(dist_x>d[x]) continue;
            for(auto [y,dist_y]:g[x])
            {
                int new_d=dist_y+dist_x;
                if(new_d<d[y])
                {
                    d[y]=new_d;
                    q.emplace(new_d,y);
                }
            }
        }
        return d[n2]==INT_MAX?-1:d[n2];
    }
};
